"""
https://leetcode.cn/problems/sort-an-array/description/

912. 排序数组
中等
相关标签
相关企业
给你一个整数数组 nums，请你将该数组升序排列。

你必须在 不使用任何内置函数 的情况下解决问题，时间复杂度为 O(nlog(n))，并且空间复杂度尽可能小。

 

示例 1：

输入：nums = [5,2,3,1]
输出：[1,2,3,5]
示例 2：

输入：nums = [5,1,1,2,0,0]
输出：[0,0,1,1,2,5]
 

提示：

1 <= nums.length <= 5 * 104
-5 * 104 <= nums[i] <= 5 * 104
"""

from typing import List


class Solution:
    def merge(self, arr1:List[int],arr2:List[int])->List[int]:
        i1=i2=0
        res=[]
        while i1<len(arr1) and i2<len(arr2):
            if arr1[i1]<=arr2[i2]:
                res.append(arr1[i1])
                i1+=1
            else:
                res.append(arr2[i2])
                i2+=1
        
        while i1<len(arr1):
            res.append(arr1[i1])
            i1+=1

        while i2<len(arr2):
            res.append(arr2[i2])
            i2+=1

        return res

    def split_sort(self,nums:List[int],left:int,right:int)->List[int]:
        """
        left,right，采用左包右不包原则
        """
        if left==right-1:
            return [nums[left]]
        
        mid=(left+right)//2
        # 先拆分
        left_arr=self.split_sort(nums,left,mid)
        right_arr=self.split_sort(nums,mid,right)

        # 再合并
        return self.merge(left_arr,right_arr)

    def sortArray(self, nums: List[int]) -> List[int]:
        """
        原始排序题
        个人比较喜欢归并排序，故再复习此法
        """
        return self.split_sort(nums,0,len(nums))

if __name__=='__main__':
    sol=Solution()
    nums=[5,1,1,2,0,0]
    res=sol.sortArray(nums)
    print(res)
    pass